from algo.sort.merge import MergeSort
from utils.bit_op import BitOp
from utils.generator import Generator
from utils.profile import Profile


class ReversePairs(MergeSort):
    # ref: https://www.bilibili.com/video/BV1L14y1B7ef/?spm_id_from=autoNext&vd_source=ad559e41b561d48861f70d0187e51e02
    # 40:00
    def __init__(self, arr):
        super(ReversePairs, self).__init__(arr)

    def raw_pairs(self):
        result = 0
        for i in range(self.len):
            s = 0
            for j in range(i + 1, self.len):
                if int(self.arr[i]) > int(self.arr[j]) << 1:
                    s += 1
            result += s
        return result

    @Profile()
    def pairs(self, left=None, right=None):
        left = 0 if left is None else left
        right = self.len - 1 if right is None else right
        if left == right:
            return 0
        middle = BitOp.middle(left, right)
        return self.pairs(left, middle) + self.pairs(middle + 1, right) + self.merge(left, middle, right)

    @Profile()
    def merge(self, left, middle, right):
        result = 0
        j = middle + 1
        i = left
        while i <= middle:
            while (j <= right) and (int(self.arr[i]) > int(self.arr[j]) << 1):
                j += 1
            result += j - middle - 1
            i += 1
        super(ReversePairs, self).merge(left, middle, right)
        return result


if __name__ == '__main__':
    arr = Generator().do()
    print(arr)
    pairs1 = ReversePairs(arr).raw_pairs()
    pairs2 = ReversePairs(arr).pairs()
    print(arr)
    print(pairs1, pairs2, pairs1 == pairs2)
